Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

  1. '?' Matches any single character.
  2. '*' Matches any sequence of characters (including the empty sequence).
  4. The matching should cover the entire input string (not partial).
  6. The function prototype should be:
  7. bool isMatch(const char *s, const char *p)
  9. Some examples:
  10. isMatch("aa","a") → false
  11. isMatch("aa","aa") → true
  12. isMatch("aaa","aa") → false
  13. isMatch("aa", "*") → true
  14. isMatch("aa", "a*") → true
  15. isMatch("ab", "?*") → true
  16. isMatch("aab", "c*a*b") → false

Solution:

  1. public class Solution {
  2.   public boolean isMatch(String s, String p) {
  3.     int n = s.length(), m = p.length();
  5.     boolean[][] dp = new boolean[n + 1][m + 1];
  7.     // initialize
  8.     dp[0][0] = true;
  10.     for (int j = 1; j <= m; j++) {
  11.       dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
  12.     }
  14.     for (int i = 1; i <= n; i++) {
  15.       for (int j = 1; j <= m; j++) {
  16.         if (p.charAt(j - 1) != '*') {
  17.           dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
  18.         } else {
  19.           dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
  20.         }
  21.       }
  22.     }
  24.     return dp[n][m];
  25.   }
  26. }